package attributes;

import trees.AttributeLeaf;
import trees.AttributeNode;
import trees.TreePrinter;
import utils.Util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.Map.Entry;

import coalition.filters.CoalitionFilter;


public class HierarchicalAttributes implements CoalitionFilter{

	HashMap<AttributePair, Object> isInLineOf = new HashMap<AttributePair, Object>();
	private HashMap<Integer, AttributeNode> allNodes;
	
	//these are the roots of treeRoots in the forest
	private HashMap<Integer, AttributeNode> treeRoots = new HashMap<Integer, AttributeNode>();	
	
	private HashMap<Integer, List<Integer>> childrenOfNode = new HashMap<Integer, List<Integer>>();
	
	private HashMap<AttributeNode, AttributeNode> partitions = new HashMap<AttributeNode, AttributeNode>();
	HashMap<AttributeNode, Object> nodesSeenBefore =  new HashMap<AttributeNode, Object>();
	
	private HashMap<Integer, String> dictionary;
	
	private List<Integer> treeRootIndices;

	
	public HashMap<Integer, AttributeNode> getTrees() {
		return treeRoots;
	}
	
	public HashMap<Integer, String> getDictionary() {
		return dictionary;
	}

	private void setUpTreeRootMap(){
		for(Integer rootIndex : treeRootIndices){
			treeRoots.put(rootIndex, allNodes.get(rootIndex));
		}
	}	

	//this method says whether a given combination of
	//attributes is legal.  All attribute combinations
	//are legal as long as they are not none is
	//a dircet or indirect child or parent of the other
	@Override
	public boolean keep(List<Integer> combination) {
		String combString = Util.printListOfIntegers(combination);
		/*
		for(int i : combination){
			for (int j : combination){
				if(i >= allNodes.size() || j >= allNodes.size())
					throw new IllegalStateException("illegal index in hierarchical attribute");
				//if(isInLineOf(combination.get(i), combination.get(j)))
				if(isInLineOf(i, j)){
					System.out.println("reject: " + combString);
					return false;
				}
			}
		}
		*/
		for(int i = 0; i < combination.size(); i++){
			for (int j = i + 1; j < combination.size(); j++){
				if(i >= allNodes.size() || j >= allNodes.size())
					throw new IllegalStateException("illegal index in hierarchical attribute");
				if(isInLineOf(combination.get(i), combination.get(j))){
				//if(isInLineOf(i, j)){
					System.out.println("reject: " + combString);
					return false;
				}
			}
		}		
		System.out.println("keep: " + combString);
		return true;
	}		
	
	public boolean isInLineOf(Integer child, Integer parent){
		return ( isInLineOf.get(new AttributePair(child, parent)) != null );
	}
	
	public List<Integer> getChildrenOfNode(Integer i){
		return childrenOfNode.get(i);
	}
	
	/*
	public HierarchicalAttributes(AttributeNode tree){
		this.tree = tree;
		traverseAttributeTree(this.tree);
		constructPartitions();
	}
	*/
	
	public HierarchicalAttributes(AttributeGraphPlusDictionary attributeGraphPlusDictionary){
		
		allNodes = attributeGraphPlusDictionary.getAllNodes();
		treeRootIndices = attributeGraphPlusDictionary.getRoots();
		setUpTreeRootMap();
		this.dictionary = attributeGraphPlusDictionary.getDictionary();
		assignRootsToPartitions();
		
		/*
		TreePrinter treePrinter = new TreePrinter(dictionary);
		for(AttributeNode tree : treeRoots.values()){
			treePrinter.printTree(tree);
		}
		*/
		
		for(AttributeNode tree : treeRoots.values()){
			traverseAttributeTree(tree);
			//treePrinter.printTree(tree);
		}
		
		
	}	
	
	private void assignRootsToPartitions(){
		for(AttributeNode tree : treeRoots.values()){
			partitions.put(tree, tree);
		}
	}
	
	//check that we are not seeing the same node again
	//which would imply a directed cycle or overlapping trees
	//which is an undirected cycle
	private void seeNode(AttributeNode attributeNode){
		if(nodesSeenBefore.get(attributeNode) != null)
			throw new IllegalArgumentException("attribute forest is not a set of treeRoots");
		else
			nodesSeenBefore.put(attributeNode, new Object());
	}
	
	private void traverseAttributeTree(AttributeNode node){
		Stack<Integer> stack = new Stack<Integer>();
		traverseAttributeTreeRecursively(stack, node);
	}
	
	private void connectGraph(){
		
	}
	
	//depth order traversal of tree to accumulate all ancestor-descendant pairs
	private void traverseAttributeTreeRecursively(Stack<Integer> stack, AttributeNode tree){
		
		//make sure we've never seen this node before
		//this algorithm should visit each node exactly once
		//if the treeRoots are the root of non-overlapping trees
		seeNode(tree);
		//create the container for the indices of children of this node
		childrenOfNode.put(tree.getAttribute(), new ArrayList<Integer>());
		//the parent node of this node was already processed
		//so will already be in the partition map
		AttributeNode parentPartitionNode = partitions.get(tree);
		
		Integer nodeAttribute = tree.getAttribute();
		
		stack.push(nodeAttribute);
		
		Iterator<Integer> attributesIterator = stack.iterator();
		Iterable<Integer> attributes = new IterableIterator<Integer>(attributesIterator);
		for(Integer ancestorAttribute : attributes){
			isInLineOf.put(new AttributePair(ancestorAttribute, nodeAttribute), new Object());
			isInLineOf.put(new AttributePair(nodeAttribute, ancestorAttribute), new Object());
			//only include leaf nodes as concrete children
			//since only leaf nodes represent real crossSection attributes
			if(tree instanceof AttributeLeaf)
				childrenOfNode.get(ancestorAttribute).add(tree.getAttribute());
		}
		
		List<AttributeNode> children = tree.getChildren();
		
		
		int positionWithinSiblings = 0;
		for(AttributeNode childNode : children){
			
			childNode.setPositionWithinSiblings(positionWithinSiblings);
			positionWithinSiblings++;
			
			partitions.put(childNode, parentPartitionNode);
			

			traverseAttributeTreeRecursively(stack, childNode);
			
		}
		stack.pop();
	}
	
	public void printTrees(){
		TreePrinter treePrinter = new TreePrinter(dictionary);
		for(AttributeNode node : treeRoots.values()){
			treePrinter.printTree(node);
		}
	}
	
}

//Java has no native tuples;  this class is really just a tuple with structural equality defined
class AttributePair{
	
	private Integer attribute1;
	private Integer attribute2;
	
	public AttributePair(Integer attribute1, Integer attribute2){
		this.attribute1 = attribute1;
		this.attribute2 = attribute2;
	}
	
    public boolean equals(Object obj){
    	if (obj instanceof AttributePair){
    		AttributePair attributePair = (AttributePair)obj;
    		return this.attribute1.equals(attributePair.attribute1) &&
    		this.attribute2.equals(attributePair.attribute2);
    	} else
    		return false;
    		
    }
    
    public String toString(){
    	return "AttributePair( " + attribute1 + ", " + attribute2 + " )";
    }
    
    public int hashCode(){
    	//assume we never have more than 64 attributes
    	//even if we do, this will just cause has chaining
    	//but and slowness but correctness will still
    	//hold due to .equals overridden method correctness
    	return this.attribute1 + this.attribute2*64; 
    }

}

//standard solution for wrapping an iterator in an iterable for classes that
//expect an iterable
class IterableIterator<T> implements Iterable<T> {
    private Iterator<T> iter;

    public IterableIterator(Iterator<T> iter) {
        this.iter = iter;
    }

    public Iterator<T> iterator() {
        return iter;
    }
}